# 希尔排序
# 自己写的算法 实现太复杂

from utils.array_utils import sjlb, check


def shell(array):
    half = len(array) // 2
    while half >= 1:
        # print('half = ', half)
        for i in range(half):
            # print(array[i], array[i+half])
            j = 0
            indexes = []
            while (i + j * half) < len(array):
                # print(array[i + j * half], end=' ')
                indexes.append(i + j * half)
                j += 1
            insert_sort_by_indexes(array,indexes)
            # print(indexes)
            # print(array)
        half //= 2


def insert_sort_by_indexes(arr, indexes_list):
    '''
    根据给定的存储了下标的列表(indexes_list), 对存储数据的列表(arr)进行插入排序
    :param arr:
    :param indexes_list:
    :return: 返回排好序的列表
    '''
    temp = []
    # 根据indexes列表中的下标值排序
    # 获取数据
    for i in indexes_list:
        value = arr[i]
        temp.append(value)
    # 插入排序
    new = []
    while temp:
        new.append(temp.pop(0))
        i = len(new) - 1
        while i > 0 and new[i] < new[i - 1]:
            new[i], new[i - 1] = new[i - 1], new[i]
            i -= 1
    # print('new:', new)
    temp = new

    # 将排好序的数据写回原列表
    for i, v in enumerate(indexes_list):
        arr[v] = temp[i]

    # print(arr)
    # print(temp)


if __name__ == '__main__':
    # l = [40, 82, 17, 35, 52, 73, 54, 9, 1]
    # shell(l)
    # print(l)
    # indexes = [0, 4, 8]
    # insert_sort_by_indexes(l, indexes)

    for i in range(1000):
        l = sjlb()
        # print(l)
        shell(l)
        if not check(l):
            print('wrong: ', l)
